BTNode* BinaryTreeFind(BTNode* root, int x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* leftroot = BinaryTreeFind(root->left, x);
	BTNode* rightroot = BinaryTreeFind(root->right, x);
	if (leftroot)
		return leftroot;
	if (rightroot)
		return rightroot;
	return NULL;

}
class Solution {
public:
	bool isUnivalTree(TreeNode* root) {
		if (root == nullptr)
			return true;
		if (root->left && root->left->val != root->val)
			return false;
		if (root->right && root->right->val != root->val)
			return false;
		return isUnivalTree(root->left) && isUnivalTree(root->right);
	}
};
class Solution {
public:
	bool is(TreeNode* rootleft, TreeNode* rootright) {
		if (rootleft == nullptr && rootright == nullptr)
			return true;
		if (rootleft == nullptr || rootright == nullptr)
			return false;
		if (rootleft->val != rootright->val)
			return false;
		return is(rootleft->left, rootright->right) && is(rootleft->right, rootright->left);

	}
	bool isSymmetric(TreeNode* root) {
		return  is(root->left, root->right);











	}
}; int BinaryTreeSize(struct TreeNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
void aapreorderTraversal(int* a, int* i, struct TreeNode* root)
{
	if (root == NULL)
		return;
	a[(*i)++] = root->val;
	aapreorderTraversal(a, i, root->left);
	aapreorderTraversal(a, i, root->right);
}



int* preorderTraversal(struct TreeNode* root, int* returnSize) {
	*returnSize = BinaryTreeSize(root);
	int* a = (int*)malloc(*returnSize * sizeof(int));
	int i = 0;
	aapreorderTraversal(a, &i, root);
	return a;



}class Solution {
public:
	bool isSameTree(TreeNode* p, TreeNode* q) {
		if (p == NULL && q == NULL)
			return true;
		if (p == NULL || q == NULL)
			return false;
		if (p->val != q->val)
			return false;
		return  isSameTree(p->left, q->left) && isSameTree(p->right, q->right);








	}
	bool isSubtree(TreeNode* root, TreeNode* subRoot) {
		if (root == nullptr)
			return false;
		if (isSameTree(root, subRoot))
			return true;


		return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);


	}
};